//有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是： 
//
// 
// 一块砖直接连接到网格的顶部，或者 
// 至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时 
// 
//
// 给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消
//失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。 
//
// 返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。 
//
// 注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
//输出：[2]
//解释：
//网格开始为：
//[[1,0,0,0]，
// [1,1,1,0]]
//消除 (1,0) 处加粗的砖块，得到网格：
//[[1,0,0,0]
// [0,1,1,0]]
//两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
//[[1,0,0,0],
// [0,0,0,0]]
//因此，结果为 [2] 。
// 
//
// 示例 2： 
//
// 
//输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
//输出：[0,0]
//解释：
//网格开始为：
//[[1,0,0,0],
// [1,1,0,0]]
//消除 (1,1) 处加粗的砖块，得到网格：
//[[1,0,0,0],
// [1,0,0,0]]
//剩下的砖都很稳定，所以不会掉落。网格保持不变：
//[[1,0,0,0], 
// [1,0,0,0]]
//接下来消除 (1,0) 处加粗的砖块，得到网格：
//[[1,0,0,0],
// [0,0,0,0]]
//剩下的砖块仍然是稳定的，所以不会有砖块掉落。
//因此，结果为 [0,0] 。 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 200 
// grid[i][j] 为 0 或 1 
// 1 <= hits.length <= 4 * 104 
// hits[i].length == 2 
// 0 <= xi <= m - 1 
// 0 <= yi <= n - 1 
// 所有 (xi, yi) 互不相同 
// 
// Related Topics 并查集 
// 👍 95 👎 0
#include <iostream>
#include <vector>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Djset{
public:
    vector<int> parent,nodeCount; // 记录节点的根
    vector<int> rank; // 记录根节点的深度（用于优化）
    int count;
    //init
    Djset(int n): parent(n), nodeCount(n){
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            nodeCount[i] = i;
        }
    }
    int Find_set(int x){
        /*
        if (parent[x] != x){
            parent[x] = Find_set(parent[x]);
        }
        return parent[x];
         */
        if (parent[x] == x){
            return parent[x];
        }
        int newPar = Find_set(parent[x]);
        parent[x] = newPar;
        return parent[x];
    }
    void Union_set(int x , int y){
        int fx = Find_set(x);
        int fy = Find_set(y);
       if (fx == fy){
           return;
       }
       parent[fx] = fy;
       nodeCount[fy] += nodeCount[fx];
    }
    bool SameRoot(int x,int y){
        return Find_set(x) == Find_set(y);
    }

    int Get_count(int x){
        return nodeCount[Find_set(x)];
    }
};
class Solution {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        int hight = grid.size() , width = grid[0].size();

        Djset ds(hight*width+1);

        vector<vector<int>> status = grid;

        for (int i = 0; i < hits.size(); i++) {
            status[hits[i][0]][hits[i][1]] = 0;
        }
        for (int i = 0; i < hight; i++) {
            for (int j = 0; j < width; j++) {
                if (status[i][j] == 1){
                    if (i == 0){
                        ds.Union_set(hight*width,i*width+j);
                    }
                    if (i > 0 && status[i-1][j] == 1){
                        ds.Union_set(i*width+j,(i-1)*width+j);
                    }
                    if (j > 0 && status[i][j-1] == 1){
                        ds.Union_set(i*width+j,i*width+j-1);
                    }
                }
            }
        }

        const vector<pair<int, int>> directions{{0, 1},{1, 0},{0, -1},{-1, 0}};
        vector<int> res(hits.size(),0);

        for (int i = hits.size()-1; i >= 0; i--) {
            int r = hits[i][0],c = hits[i][1];
            if (grid[r][c] == 0){
                continue;
            }

            int pre = ds.Get_count(hight*width);

            if (r == 0) {
                ds.Union_set(c,hight*width);
            }
            for (const auto [dr,dc] : directions){
                int newDirR = r + dr,newDirC = c + dc;

                if (newDirR >= 0 && newDirR < hight && newDirC >= 0 && newDirC < width){
                    if (status[newDirR][newDirC] == 1){
                        ds.Union_set(r*width+c,newDirR*width+newDirC);
                    }
                }
            }
            res[i] = max(0,ds.Get_count(hight*width)-pre-1);
            status[r][c] = 1;
        }
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
